/**
 * 给你 k 种面值的硬币，面值分别为 c1, c2 ... ck，每种硬币的数量无限，再给一个总金额 amount。
 * 问你最少需要几枚硬币凑出这个金额，
 * 如果不可能凑出，算法返回 -1 。
 * 
 * 算法的函数签名如下：
 * coins 中是可选硬币面值，amount 是目标金额
 * int coinChange(int[] coins, int amount);
 * 比如说 k = 3，面值分别为 1，2，5，总金额 amount = 11。那么最少需要 3 枚硬币凑出，即 11 = 5 + 5 + 1。
 */

// 自顶而下
// function coinChange(coins, amount) {
//     var dp = function (amount, arr) {
//         if (arr[amount] !== undefined) {
//             return arr[amount];
//         }
//         if (amount === 0) {
//             return 0;
//         }
//         if (amount < 0) {
//             return -1;
//         }
//         var res = Infinity;
//         for (const coin of coins) {
//             var sub = dp(amount - coin, arr); //递归减去其中一个钱币的金额，则意味着，当前的最小值就是该结果+1
//             if (sub === -1) {
//                 continue;
//             }
//             res = Math.min(res, 1 + sub);
//         }
//         arr[amount] = res;
//         if (res === Infinity) {
//             return -1;
//         }
//         return res;
//     };

//     return dp(amount, []);
// };

// 自下而上
function coinChange(coins, amount) {
    if (amount < 0) {
        return -1;
    }
    if (amount === 0) {
        return 0;
    }
    var count = amount + 1;
    var dp = new Array(count).fill(count);
    dp[0] = 0;
    for (let i = 0; i < count; i++) {
        for (const coin of coins) {
            if (i - coin < 0) {
                continue;
            }
            dp[i] = Math.min(dp[i], 1 + dp[i - coin]); //递归减去其中一个钱币的金额，则意味着，当前的最小值就是该结果+1
        }
    }
    return dp[amount];
};

var coins = [5, 3, 4];
var amount = 11;
// var amount = 3; 
// 为2时，需要-1
// 为3时，需要1
// 为4时，需要1
// 为5时，需要1
// 为6时，需要1+1

console.log(coinChange(coins, amount));